package algorithm.middle;

import pojo.TreeNode;

import java.util.*;

/**
 * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 * <p>
 * 创建一个根节点，其值为 nums 中的最大值。
 * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * 返回 nums 构建的 最大二叉树 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ConstructMaximumBinaryTree654 {
    //递归 DFS
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int max = -1;
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                index = i;
                max = nums[index];
            }
        }
        TreeNode root = new TreeNode(nums[index]);
        if (index > 0) {
            int[] left = Arrays.copyOfRange(nums, 0, index);
            root.left = constructMaximumBinaryTree(left);
        }
        if (index + 1 < nums.length) {
            int[] right = Arrays.copyOfRange(nums, index + 1, nums.length);
            root.right = constructMaximumBinaryTree(right);
        }
        return root;
    }

    //单调栈 O(n)

    /**
     * 1> 如果栈顶元素大于待插入的元素，那么直接入栈。
     * 2> 如果栈顶元素小于待插入的元素，那么栈顶元素出栈。
     * 依题意有：
     * 1> 如果栈顶元素大于待插入的元素，则：栈顶元素.right = 待插入元素。
     * 2> 如果栈顶元素小于待插入的元素，则：待插入元素.left = 栈顶元素。
     */

    public TreeNode constructMaximumBinaryTree2(int[] nums) {
        Stack<TreeNode> stack = new Stack<>();
        out: for (int x : nums) {
            TreeNode node = new TreeNode(x);
            if (stack.isEmpty()) {
                stack.push(node);
            } else {
                TreeNode peek = stack.peek();
                //如果栈顶元素小于待插入的元素
                while (peek.val < node.val) {
                    TreeNode pop = stack.pop();
                    node.left = pop;
                    if (stack.isEmpty()) {
                        stack.push(node);
                        continue out;
                    }
                    peek = stack.peek();
                }
                //此处s栈顶元素大于待插入元素
                stack.push(node);
                peek.right = node;
            }
        }
        TreeNode res = null;
        while (!stack.isEmpty()){
            res =  stack.pop();
        }
        return res;

    }

}
